#[test]
fn test_letter_combinations() {
    assert_eq!(letter_combinations(String::from("")), vec![""; 0]);
    assert_eq!(letter_combinations(String::from("2")), vec!["a", "b", "c"]);
    assert_eq!(letter_combinations(String::from("3")), vec!["d", "e", "f"]);
    assert_eq!(
        letter_combinations(String::from("23")),
        vec!["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
    );
}
/*
    17. 电话号码的字母组合
    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

    给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

    示例 1：
    输入：digits = "23"
    输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

    示例 2：
    输入：digits = ""
    输出：[]

    示例 3：
    输入：digits = "2"
    输出：["a","b","c"]

    提示：
    0 <= digits.length <= 4
    digits[i] 是范围 ['2', '9'] 的一个数字。
*/
use std::collections::HashMap;

#[macro_export]
macro_rules! hashmap {
    ($($key: expr => $val: expr),*) => {
        {
            let mut map = HashMap::new();
            $(map.insert($key, $val);)*
            map
        }
    };
}

pub fn letter_combinations(digits: String) -> Vec<String> {
    let map = hashmap! {
        b'2' => "abc",
        b'3' => "def",
        b'4' => "ghi",
        b'5' => "jkl",
        b'6' => "mno",
        b'7' => "pqrs",
        b'8' => "tuv",
        b'9' => "wxyz"
    };
    let mut res = vec![];
    backtrack(&digits, &mut res, &mut vec![], &map);
    res
}

fn backtrack<'a>(
    digits: &str,
    res: &mut Vec<String>,
    buf: &mut Vec<&'a str>,
    map: &'a HashMap<u8, &str>,
) {
    let digit = match digits.as_bytes().first() {
        Some(it) => it,
        _ => {
            if !buf.is_empty() {
                res.push(buf.iter().map(|&s| s).collect());
            }
            return;
        }
    };

    let mapping = map[digit];
    for i in 0..mapping.len() {
        buf.push(&mapping[i..=i]);
        backtrack(&digits[1..], res, buf, map);
        buf.pop();
    }
}
